package com.lft.graph04.shortest_path_graph02_floyd;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 无向图的实现——邻接表
 */
public class GraphAdjacencyList<E> implements GraphInterface<E> {
	/**
	 * 邻接表中对就的链表的顶点
	 */
	private static class EdgeNode {
		/**
		 * 邻接顶点的索引
		 */
		int adjVertexIndex;
		
		/**
		 * 存储边或弧相关的信息，如权值。
		 */
		int weight;
		
		/**
		 * 该顶点的下一个邻接头顶点
		 */
		EdgeNode nextAdjNode;
		
		/**
		 * 构造器，初始化当前节点的 索引，权重值。
		 * @param adjVertexNo
		 * @param weight
		 */
		public EdgeNode(int adjVertexNo, int weight) {
			this.adjVertexIndex = adjVertexNo;
			this.weight = weight;
		}
	}
	
	/**
	 * 邻接表中表的顶点。
	 * @param <E>
	 */
	private static class VertexNode<E> {
		/**
		 * 顶点数据信息
		 */
		E data;
		
		/**
		 * 邻接表的第1个顶点
		 */
		EdgeNode firstAdj;
	}
	
	/**
	 * 存储各个顶点最短路径的信息
	 */
	private Distance[] dis;
	
	/**
	 * 顶点数组
	 */
	private VertexNode<E>[] vertexs;
	/**
	 * 顶点的实际数量。
	 */
	private int numOfVertexs;
	
	/**
	 * 顶点的最大数量。
	 */
	private int maxNumOfVertexs;
	
	/**
	 * 判断顶点是否被访问过。true：访问过；false：未访问过。
	 */
	private boolean[] visited;
	
	public GraphAdjacencyList(int maxNumOfVertexs) {
		this.maxNumOfVertexs = maxNumOfVertexs;
		vertexs = (VertexNode<E>[]) Array.newInstance(VertexNode.class, maxNumOfVertexs);
	}
	
	/**
	 * 获取顶点的个数。
	 * @return
	 */
	@Override
	public int getNumOfVertex() {
		return numOfVertexs;
	}
	
	/**
	 * 插入顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean insertVertex(E v) {
		if (numOfVertexs >= maxNumOfVertexs) {
			return false;
		}
		VertexNode<E> vertex = new VertexNode<>();
		vertex.data = v;
		vertexs[numOfVertexs++] = vertex;
		return true;
	}
	
	/**
	 * 删除顶点
	 * @param v 要删除顶点的数据
	 * @return
	 */
	@Override
	public boolean deleteVertex(E v) {
		// 遍历顶点数组。
		for (int i = 0; i < numOfVertexs; i++) {
			// 如果当前顶点数组的值跟要查找的值相等。找到了要删除的顶点
			if (vertexs[i].data.equals(v)) {
				// 循环将要删除顶点后面的顶点往前移覆盖要删除的顶点。
				for (int j = i; j < numOfVertexs - 1; j++) {
					vertexs[j] = vertexs[j + 1];
				}
				// 将最后一项顶点置空。
				vertexs[numOfVertexs - 1] = null;
				// 顶点数量减1
				numOfVertexs--;
				// 临时顶点cur,表示当前顶点。
				EdgeNode cur;
				// 临时顶点pre,表示当前顶点的前一个顶点。
				EdgeNode pre;
				// 遍历每一个顶点，将顶点表中的每个顶点的第一个邻接顶点的索引是删除顶点索引的都删除。
				for (int j = 0; j < numOfVertexs; j++) {
					// 如果当前顶点没有邻接头顶点。
					if (vertexs[j].firstAdj == null) {
						// 继续往后查找删除。
						continue;
					}
					// 如果当前顶点的邻接的对头顶点的索引正好是 删除顶点的索引。
					if (vertexs[j].firstAdj.adjVertexIndex == i) {
						// 将邻接头顶点置空。不指向删除的顶点。
						vertexs[j].firstAdj = null;
						// 继续往后查找删除。
						continue;
					}
					// 将临时指针指向当前顶点的邻接头顶点。
					cur = vertexs[j].firstAdj;
					//循环遍历邻接顶点的链表。
					while (cur != null) {
						// 先将 前一个头顶点指向 cur.
						pre = cur;
						// 将 cur 指向 后一个头顶点。
						cur = cur.nextAdjNode;
						// 如果 cur 不为空。且 cur的邻接头顶点的索引 正好是要删除顶点的索引。
						if (cur != null && cur.adjVertexIndex == i) {
							// 将 pre 顶点的邻接头顶点 指向 cur 顶点的邻接头顶点。
							pre.nextAdjNode = cur.nextAdjNode;
							// 跳出当前while循环。
							break;
						}
					}
				}
				// 遍历每一个顶点，删除了那个顶点后，其他在删除顶点后的顶点索引要前移。
				for (int j = 0; j < numOfVertexs; j++) {
					// cur 指向当前顶点的邻接头顶点。
					cur = vertexs[j].firstAdj;
					// 循环遍历
					while (cur != null) {
						// 只要cur的邻接头顶点的索引 > 删除的顶点的索引
						if (cur.adjVertexIndex > i) {
							// 将索引-1
							cur.adjVertexIndex--;
						}
						// 后移继续遍历
						cur = cur.nextAdjNode;
					}
				}
				// 操作完之后表示删除顶点成功。
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 定位顶点的位置
	 * @param v 要查找的顶点。
	 * @return -1 未找到。其他值就是顶点的索引。
	 */
	@Override
	public int indexOfVertex(E v) {
		// 循环遍历
		for (int i = 0; i < numOfVertexs; i++) {
			// 当前顶点的数据 == 要查找的数据
			if (vertexs[i].data.equals(v)) {
				// 返回当前索引
				return i;
			}
		}
		// 没找到 返回-1
		return -1;
	}
	
	/**
	 * 查找指定位置的顶点的值
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public E valueOfVertex(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex > numOfVertexs) {
			return null;
		}
		return vertexs[vertexIndex].data;
	}
	
	/**
	 * 检查边的索引和权重值是否合法
	 * @param v1
	 * @param v2
	 * @param weight
	 * @return
	 */
	@Override
	public boolean checkEdgeValue(int v1, int v2, int weight) {
		if (v1 < 0 || v1 > numOfVertexs || v2 < 0 || v2 > numOfVertexs || weight < 0) {
			return false;
		}
		return true;
	}
	
	/**
	 * 插入边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @param weight       权重 1表示连接。0表示不通。
	 * @return
	 */
	@Override
	public boolean insertEdge(int vertexIndex1, int vertexIndex2, int weight) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		if (weight == 0) {
			return false;
		}
		// 无向图，先往 vertexIndex1 索引的顶点 插入 vertexIndex2 索引的顶点。
		// 用 vertexIndex2 索引 和 weight 权重 创建一个临时 顶点。
		EdgeNode vertex1 = new EdgeNode(vertexIndex2, weight);
		// 如果 vertexIndex1 索引的顶点 没有邻接顶点。
		if (vertexs[vertexIndex1].firstAdj == null) {
			// 直接将要插入的 vertex1 放在 vertexIndex1 顶点的邻接头顶点位置上。
			vertexs[vertexIndex1].firstAdj = vertex1;
		}
		// 如果 vertexIndex1 索引的顶点 有邻接顶点。
		else {
			// 采用头插法。将原来的邻接头顶点赋值给 新顶点
			vertex1.nextAdjNode = vertexs[vertexIndex1].firstAdj;
			// 再将新顶点赋值给 vertexIndex1 顶点的邻接头顶点。
			vertexs[vertexIndex1].firstAdj = vertex1;
		}
		
		// 再往 vertexIndex2 索引的顶点 插入 vertexIndex1 索引的顶点。
		EdgeNode vertex2 = new EdgeNode(vertexIndex1, weight);
		// 如果 vertexIndex2 索引的顶点 没有邻接顶点。
		if (vertexs[vertexIndex2].firstAdj == null) {
			// 直接将要插入的 vertex2 放在 vertexIndex2 顶点的邻接头顶点位置上。
			vertexs[vertexIndex2].firstAdj = vertex2;
		}
		// 如果 vertexIndex2 索引的顶点 有邻接顶点。
		else {
			// 采用头插法。
			// 将原来的邻接头顶点赋值给 新顶点
			vertex2.nextAdjNode = vertexs[vertexIndex2].firstAdj;
			// 再将新顶点赋值给 vertexIndex2 顶点的邻接头顶点。
			vertexs[vertexIndex2].firstAdj = vertex2;
		}
		return true;
	}
	
	/**
	 * 删除边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return
	 */
	@Override
	public boolean deleteEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 删除索引为index1的顶点与索引为index2的顶点之间的边
		EdgeNode cur = vertexs[vertexIndex1].firstAdj;
		EdgeNode pre = null;
		// 删除索引为 vertexIndex1 的顶点与索引为 vertexIndex2 的顶点之间的边
		while (cur != null && cur.adjVertexIndex != vertexIndex2) {
			pre = cur;
			cur = cur.nextAdjNode;
		}
		if (cur != null) {
			pre.nextAdjNode = cur.nextAdjNode;
		}
		
		// 删除索引为 vertexIndex2 的顶点与索引为 vertexInde1 的顶点之间的边
		cur = vertexs[vertexIndex2].firstAdj;
		while (cur != null && cur.adjVertexIndex != vertexIndex1) {
			pre = cur;
			cur = cur.nextAdjNode;
		}
		if (cur != null) {
			pre.nextAdjNode = cur.nextAdjNode;
		}
		return true;
	}
	
	/**
	 * 查找顶点1与顶点2边的权值
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return
	 */
	@Override
	public int getEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new IndexOutOfBoundsException();
		}
		EdgeNode cur = vertexs[vertexIndex1].firstAdj;
		while (cur != null) {
			if (cur.adjVertexIndex == vertexIndex2) {
				return cur.weight;
			}
			cur = cur.nextAdjNode;
		}
		return 0;
	}
	
	/**
	 * 邻接表-深度优先搜索遍历——基于栈实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String depthFirstSearchByStack(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 初始化 访问标记数组
		visited = new boolean[numOfVertexs];
		// 创建 StringBuilder 对象，用于遍历输出打印。
		StringBuilder sb = new StringBuilder();
		// 创建一个栈，入栈出栈的是索引。
		Stack<Integer> stack = new Stack<>();
		// 先将当前顶点的索引压入栈中。
		stack.push(vertexIndex);
		// 将当前索引的访问标记设置为 true
		visited[vertexIndex] = true;
		// 创建一个临时顶点。
		EdgeNode cur;
		// 只要栈不为空，循环遍历
		while (!stack.isEmpty()) {
			// 弹出栈顶索引。赋值给 vertexIndex
			vertexIndex = stack.pop();
			// 将 vertexIndex 索引下的顶点的值拼接到 sb 中。
			sb.append(vertexs[vertexIndex].data + ",");
			// 将 cur 指向 vertexIndex 索引下顶点的邻接顶点。
			cur = vertexs[vertexIndex].firstAdj;
			// 只要 cur 不为空。循环
			while (cur != null) {
				// 如果 邻接顶点的访问标志 不为true
				if (!visited[cur.adjVertexIndex]) {
					// 将 邻接顶点的索引 压入栈中。
					stack.push(cur.adjVertexIndex);
					// 修改 访问标志
					visited[cur.adjVertexIndex] = true;
				}
				// 继续后移，看下一个邻接顶点。
				cur = cur.nextAdjNode;
			}
		}
		// sb 长度大于0，将 sb 从头到尾返回，否则返回 null
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接表-深度优先搜索遍历——基于递归
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String depthFirstSearchByRecursion(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		visited = new boolean[numOfVertexs];
		StringBuilder sb = new StringBuilder();
		depthFirstSearchByRecursion(vertexIndex, sb);
		// 如果图是非连通图，那么我们这里还需要对每个顶点遍历一次，保证全部顶点都被访问到了。
		for (int i = 0; i < numOfVertexs; i++) {
			// 如果有顶点没有被访问过。调用递归方法访问一下。
			if (!visited[i]) {
				depthFirstSearchByRecursion(i, sb);
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接表-用于递归DFS遍历
	 * @param vertexIndex
	 * @param sb
	 * @return
	 */
	private StringBuilder depthFirstSearchByRecursion(int vertexIndex, StringBuilder sb) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		sb.append(vertexs[vertexIndex].data + ",");
		visited[vertexIndex] = true;
		// 找到下一个未被访问的顶点
		EdgeNode nextNode = vertexs[vertexIndex].firstAdj;
		while (nextNode != null) {
			if (!visited[nextNode.adjVertexIndex]) {
				depthFirstSearchByRecursion(nextNode.adjVertexIndex, sb);
			} else {
				nextNode = nextNode.nextAdjNode;
			}
		}
		return sb;
	}
	
	/**
	 * 邻接表-广度优先搜索遍历——基于队列实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String breadFirstSearchByStack(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 初始化访问标志
		visited = new boolean[numOfVertexs];
		// 用于拼接顶点数据
		StringBuilder sb = new StringBuilder();
		// 创建一个队列用于出入队索引
		Queue<Integer> queue = new LinkedList<>();
		// 调用方法进行广度优先搜索遍历
		breadFirstSearchByStack(vertexIndex, sb, queue);
		// 返回拼接后的顶点数据。
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接表-真实广度优先搜索遍历方法
	 * @param vertexIndex 开始顶点索引
	 * @param sb          用于拼接顶点数据的 StringBuilder
	 * @param queue       队列
	 * @return
	 */
	private StringBuilder breadFirstSearchByStack(int vertexIndex, StringBuilder sb, Queue<Integer> queue) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 向队列中添加当前 索引
		queue.offer(vertexIndex);
		// 将当前索引的访问标志设置为 true;
		visited[vertexIndex] = true;
		// 定义一个临时节点。
		EdgeNode cur;
		// 队列不为空，循环遍历
		while (!queue.isEmpty()) {
			// 弹出队列中的第一个索引。
			vertexIndex = queue.poll();
			// 将索引下顶点的数据拼接到 sb 中。
			sb.append(vertexs[vertexIndex].data + ",");
			// 将 cur 指向 当前顶点的邻接顶点。
			cur = vertexs[vertexIndex].firstAdj;
			// 如果邻接顶点不为空。循环遍历
			while (cur != null) {
				// 如果 cur 的索引没有被访问过。
				if (!visited[cur.adjVertexIndex]) {
					// 将索引添加进队列。
					queue.offer(cur.adjVertexIndex);
					// 将当前索引的访问标志修改为 true
					visited[cur.adjVertexIndex] = true;
				}
				// 否则 cur 后移，指向 邻接顶点。
				cur = cur.nextAdjNode;
			}
		}
		// 再遍历一次。以防有顶点没有边的情况
		for (int i = 0; i < numOfVertexs; i++) {
			if (visited[i]) {
				continue;
			} else {
				breadFirstSearchByStack(i, sb, queue);
			}
		}
		return sb;
	}
	
	/**
	 * 邻接表-最短路径算法1——迪杰斯特拉算法
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public int[] dijkstra(int vertexIndex) {
		// if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
		// 	throw new ArrayIndexOutOfBoundsException();
		// }
		// // 创建 Distance 数组
		// dis = new Distance[numOfVertexs];
		// // 初始化
		// for (int i = 0; i < numOfVertexs; i++) {
		// 	dis[i] = new Distance();
		// }
		// // 源点到所有顶点的初始距离初始化最大值。
		// for (int i = 0; i < numOfVertexs; i++) {
		// 	dis[i].path = "V" + (vertexIndex + 1) + " --> V" + (i + 1);
		// 	dis[i].value = Integer.MAX_VALUE;
		// }
		// // 定义一个临时结点 cur
		// ENode cur;
		// // cur 指向 源点的 邻接顶点。
		// cur = vertexs[vertexIndex].firstAdj;
		// // 循环遍历
		// while (cur != null) {
		// 	// 将每个顶点的权重添加到 路径距离数组中。
		// 	dis[cur.adjVertexIndex].value = cur.weight;
		// 	// 后移遍历
		// 	cur = cur.nextAdjNode;
		// }
		// // 源点跟源点的距离设置为0
		// dis[vertexIndex].value = 0;
		// // 将 源点添加到 S 集合
		// dis[vertexIndex].visit = true;
		//
		// // 处理从源点到其余顶点的最短距离
		// for (int i = 0; i < numOfVertexs; i++) {
		// 	int min = Integer.MAX_VALUE;
		// 	int index = -1;
		// 	// 比较从源点到其他顶点的路径长度
		// 	for (int j = 0; j < numOfVertexs; j++) {
		// 		// 从源点到 j 顶点的最短路径还没找过
		// 		if (!dis[j].visit && dis[j].value < min) {
		// 			// 找到其中最小的路径
		// 			index = j;
		// 			min = dis[j].value;
		// 		}
		// 	}
		// 	// 找到源点索引为 index 顶点的最短路径长度
		// 	if (index != -1) {
		// 		dis[index].visit = true;
		// 	}
		// 	// 更新当前最短路径及距离
		// 	for (int k = 0; k < numOfVertexs; k++) {
		// 		// k 顶点还在 T 集合中，也就是未被找到最短路径。
		// 		if (dis[k].visit == false) {
		// 			// 将 cur 指向 k 顶点的邻接顶点
		// 			cur = vertexs[k].firstAdj;
		// 			while (cur != null) {
		// 				// 当前顶点的邻接顶点索引正好等于最小值索引
		// 				if (cur.adjVertexIndex == index) {
		// 					// 源点到 index 的值 + index 到 cur 的 和 小于 源点到 k
		// 					if ((min + cur.weight) < dis[k].value) {
		// 						// 更新 源点到 k 的最短路径值
		// 						dis[k].value = min + cur.weight;
		// 						dis[k].path = dis[index].path + " --> V" + (k + 1);
		// 						break;
		// 					}
		// 				}
		// 				cur = cur.nextAdjNode;
		// 			}
		// 		}
		// 	}
		// }
		return new int[0];
	}
	
	/**
	 * 邻接表-最短路径算法2——弗洛伊德算法
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public int[] floyd(int vertexIndex) {
		return new int[0];
	}
	
	/**
	 * 打印邻接表
	 */
	@Override
	public void displayGraph() {
		for (int i = 0; i < numOfVertexs; i++) {
			System.out.print(vertexs[i].data + "\t");
			EdgeNode cur = vertexs[i].firstAdj;
			while (cur != null) {
				System.out.print(vertexs[cur.adjVertexIndex].data + "\t");
				cur = cur.nextAdjNode;
			}
			System.out.println();
		}
	}
	
	/**
	 * 打印最短路径
	 */
	public void displayShortestPath(int vertexIndex) {
		dijkstra(vertexIndex);
		String str;
		str = "V" + (vertexIndex + 1);
		System.out.println("以 " + str + " 为起点的力的最短路径为：");
		for (int i = 0; i < numOfVertexs; i++) {
			if (dis[i].value != Integer.MAX_VALUE) {
				System.out.println(dis[i].path + " = " + dis[i].value);
			} else {
				System.out.println(dis[i].path + " 无最短路径。");
			}
		}
	}
}
